package com.kevinkk.stackandqueue;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * 有效字符串需满足：
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 每个右括号都有一个对应的相同类型的左括号。
 */

public class ValidParentheses {
    class Solution {
        public boolean isValid(String s) {
            Deque<Character> stack = new ArrayDeque<>();
            char[] cs = s.toCharArray();
            for (char c : cs) {
                if (c == '(') {
                    stack.addFirst(')');
                } else if (c == '[') {
                    stack.addFirst(']');
                } else if (c == '{') {
                    stack.addFirst('}');
                // 弹出之前首先需要进行非空判断
                } else if (stack.isEmpty() || c != stack.removeFirst()) {
                    return false;
                }
            }

            return stack.isEmpty();
        }
    }
}
